import math

class Car:
    buying = ""
    maint = ""
    doors = 0
    persons = 0
    lug_boot = ""
    safety = ""
    attractiveness = ""  

    def __init__(self,buying,maint,doors,persons,lug_boot,safety,attractiveness):
        self.buying = buying
        self.maint = maint
        self.doors = doors
        self.persons = persons
        self.lug_boot = lug_boot
        self.safety = safety
        self.attractiveness = attractiveness

class Attribute:
    name = ""
    Values = []

    def __init__(self,name):
        self.name = name
        self.Values = []


class DecisionFork:
    """A fork of a decision tree holds an attribute to test, and a dictionary
    of branches, one for each of the attribute's values."""

    def __init__(self, attribute, branches):
        "Initialize by saying what attribute this node tests."
        self.attribute = attribute
        self.branches = branches

    def get(self, example):
        "Given an example, return the current branch given the attribute-value"
        "combinations in this example"
        "I assume that also the example is a dictionary with the attributes "
        "as keys and the values as values"
        attrvalue = example[self.attribute]
        return self.branches[attrvalue]

    def add(self, val, subtree):
        "Add a branch for a particular value; a branch is hereby either a "
        "DecisionLeaf or another DecisionFork"
        self.branches[val] = subtree

    def display(self, indent=0):
        name = self.attribute
        print(' '*4*indent, name)
        for (val, subtree) in self.branches.items():
            print(' '*4*(indent+1), '=', val, '==>')
            subtree.display(indent + 2)

    def __repr__(self):
        return ('DecisionFork(%r, %r)'
                % (self.attribute, self.branches))



class DecisionLeaf:
    "A leaf of a decision tree holds just a result."
    def __init__(self, result):
        self.result = result

    def get(self, example):
        return self.result

    def display(self, indent=1):
        print(' '*4*indent, 'RESULT =', self.result)

    def __repr__(self):
        return repr(self.result)

CarDatabase = []
Attributes = {}

buying = Attribute('buying')
buying.Values = ['vhigh','high','med','low']
maint = Attribute('maint')
maint.Values = ['vhigh','high','med','low']
doors = Attribute('doors')
doors.Values = ['2','3','4','5more']
persons = Attribute('persons')
persons.Values = ['2','4','more']
lug_boot = Attribute('lug_boot')
lug_boot.Values = ['small','med','big']
safety = Attribute('safety')
safety.Values = ['low','med','high']

Attributes[buying] = 0
Attributes[maint] = 0
Attributes[doors] = 0
Attributes[persons] = 0
Attributes[lug_boot] = 0
Attributes[safety] = 0

def CarProcess(dataLine):
    mylist = []
    mylist = dataLine[:-1].split(",")
    c = Car(mylist[0],mylist[1],mylist[2],mylist[3],mylist[4],mylist[5],mylist[6])
    CarDatabase.append(c)


def ReadCars(fileName):
    dataFile = open(fileName)
    for dataLine in dataFile.readlines():
        CarProcess(dataLine)
    dataFile.close()
    del dataFile

def ID3(ExamplesTable, Attributes):
   if(AllExamplesOfSameClass(ExamplesTable)):
       return DecisionLeaf(ExamplesTable[0].attractiveness)        
       
   if(len(Attributes) == 0):
       return DecisionLeaf(MostCommonClassInExamplesTable(ExamplesTable))

   else:
       for x in Attributes:
            Attributes[x] = Attributes[x] + InformationGain(ExamplesTable,x)
       A = max(Attributes, key=Attributes.get)
       Dict = {}
       DF = DecisionFork(A.name,Dict)
       for vi in A.Values:
           E_vi = []
           E_vi = CreateSubTable(ExamplesTable,A,vi)

           if(len(E_vi) == 0): 
               DF.branches[vi] = DecisionLeaf(MostCommonClassInExamplesTable(E_vi))
           else:
               TempDict = Attributes.copy()             
               del TempDict[A]
               DF.branches[vi] = ID3(E_vi,TempDict)
   return DF


def InformationGain(Examples,A):
    HS = CalculateEntropy(Examples)
    HA = 0
    for vi in A.Values:
        E_vi = []
        E_vi = CreateSubTable(Examples,A,vi)
        HA = HA + ((len(E_vi)/len(Examples)) * CalculateEntropy(E_vi))
    return HS - HA 
                

def CreateSubTable(Examples,Attribute,Value):
    SubTable = []
    for x in Examples:
        if(Attribute.name == 'buying'):
            if(x.buying == Value):
                SubTable.append(x)
        elif (Attribute.name == 'maint'):
            if(x.maint == Value):
                SubTable.append(x)
        elif (Attribute.name == 'doors'):
            if(x.doors == Value):
                SubTable.append(x)
        elif (Attribute.name == 'persons'):
            if(x.persons == Value):
                SubTable.append(x)
        elif (Attribute.name == 'lug_boot'):
            if(x.lug_boot == Value):
                SubTable.append(x)
        elif (Attribute.name == 'safety'):
            if(x.safety == Value):
                SubTable.append(x)
        elif (Attribute.name == 'attractiveness'):
            if(x.attractiveness == Value):
                SubTable.append(x)
    return SubTable
           

def CalculateEntropy(Examples):
    datavalue = {'unacc': 0, 'acc': 0, 'vgood': 0, 'good': 0}   
    HS = 0
    All = 0
    for x in Examples:
        datavalue[x.attractiveness] = datavalue[x.attractiveness] + 1
        All = All + 1
    for key in datavalue:
        if(datavalue[key] != 0):
            HS = HS - ((datavalue[key]/All) * math.log2(datavalue[key]/All))
    return HS


def AllExamplesOfSameClass(ExamplesTable):
   Temp = ExamplesTable[0].attractiveness
   for x in ExamplesTable:
       if(Temp != x.attractiveness):
           return False
   return True

def MostCommonClassInExamplesTable(ExamplesTable):
    datavalue = {'unacc': 0, 'acc': 0, 'vgood': 0, 'good': 0}    
    for x in ExamplesTable:
        if(x.attractiveness == 'unacc'):
            datavalue[x.attractiveness] = datavalue[x.attractiveness] + 1
        elif(x.attractiveness == 'acc'):
            datavalue[x.attractiveness] = datavalue[x.attractiveness] + 1
        elif(x.attractiveness == 'vgood'):
            datavalue[x.attractiveness] = datavalue[x.attractiveness] + 1
        elif(x.attractiveness == 'good'):
            datavalue[x.attractiveness] = datavalue[x.attractiveness] + 1
    return max(datavalue, key = lambda x: datavalue[x])

def GetAttributeValues(Attribute,CDBase):
    List = []
    for x in CDBase:
        if (Attribute == 'buying'):
            if x.buying not in List:
                List.append(x.buying)
        elif (Attribute == 'maint'):
            if x.maint not in List:
                List.append(x.maint)
        elif (Attribute == 'doors'):
            if x.doors not in List:
                List.append(x.doors)
        elif (Attribute == 'persons'):
            if x.persons not in List:
                List.append(x.persons)
        elif (Attribute == 'lug_boot'):
            if x.lug_boot not in List:
                List.append(x.lug_boot)
        elif (Attribute == 'safety'):
            if x.safety not in List:
                List.append(x.safety)
    return List



ReadCars("car.data")
GetAttributeValues("buying",CarDatabase)
ID3(CarDatabase,Attributes).display()


